import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

public class TestSort {

    /**
     * 插入排序：
     * 时间复杂度：[对数据敏感]
     *   最坏情况下：O(n^2)  逆序的
     *   最好情况下：数据是有序的 O(n)
     *   【直接插入排序的使用场景是：当数据量小，并且已经趋于有序的时候，使用直接插入排序】
     * 空间复杂度：O(1)
     * 稳定性：稳定的排序
     * @param array
     */
    public static void insertSort(int[] array) {
        for(int i = 1;i < array.length;i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= 0 ; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    //array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }


    public static void shell(int[] array,int gap) {
        for(int i = gap ;i < array.length;i++) {
            int tmp = array[i];
            int j = i-gap;
            for (; j >= 0 ; j -= gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

    /**
     * 希尔排序
     * 空间复杂度：O(1)
     * 稳定性：不稳定的排序
     * @param array
     */
    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            shell(array,gap);
            gap /= 2;
        }
        shell(array,1);
    }

    /**
     * 选择排序
     * 时间复杂度：
     *    不管有序无序-》O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array,minIndex,i);
        }
    }

    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    /**
     * 堆排序
     * 时间复杂度：O(n*logn)【不管数据是否有序 都是这样的】
     * 空间复杂度：O(1)
     * 稳定性：不稳定排序
     * @param array
     */
    private static void shiftDown(int[] array,int root,int len) {
        int parent = root;
        int child = (2*parent) + 1;
        while (child < len) {
            if(child+1 < len && array[child] < array[child+1]) {
                child++;
            }
            if(array[child] > array[parent]) {
                swap(array,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

    private static void createHeap(int[] array) {
        for (int p = (array.length-1-1)/2; p >= 0 ; p--) {
            shiftDown(array,p,array.length);
        }
    }


    public static void heapSort(int[] array) {
        createHeap(array);
        int end = array.length-1;
        while (end >= 0) {
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }
    /**
     * 冒泡排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * @param array
     */
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                }
            }
        }
    }

    public static void bubbleSort2(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            if(!flg) {
                break;
            }
        }
    }

    /**
     * 快速排序递归未优化
     * 时间复杂度 :
     *   最好情况 : 满二叉树 : O(n*logn)
     *   最坏情况 : 单分支树 , 树的高度等于元素的个数 : O(n^2)
     * 空间复杂度 :  O(logn) 递归的
     * 稳定性 : 不稳定
     */
     //求基准方法一 : hore法
     public static int privoid(int []arr ,int low ,int high) {
         int i = low;
         int tmp = arr[low];
         while( low < high) {
              //从左往右找比 基准大的值的位置
             while(low < high && arr[low] <= tmp) {
                 low++;
             }
             //从右左找比基准小的位置
             while( low < high && arr[high] >= tmp) {
                 high--;
             }

             //找到后交换
             swap(arr,low,high);
         }
         //当low = high 时出循环,说明low和high相遇,交换基准值和 相遇位置的值
         swap(arr,i,low);
         //交换完毕后,基准值的下标 就是low
         return low;
     }


    //求基准方法二 挖坑法
    public static int partition2(int []arr ,int low ,int high) {
        int tmp = arr[low];

        while( low <high) {
            //从右往左找 比基准大的小的值
            while( low < high && arr[high] >= tmp) {
                high--;
            }
            arr[low] = arr[high];
            //从左往右找比比基准小的值
            while( low < high && arr[low] <= tmp) {
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = tmp;
        return low;
    }

    //未优化 快速排序
    public static void quickSort(int []arr,int left ,int right) {
            if(left >= right) {
                return ;
            }
            int privot = privoid(arr,left,right);
            quickSort(arr,left,privot-1);
            quickSort(arr,privot+1,right);
    }

    //优化的快速排序代码 :
    public static void quickSort2(int []arr,int left ,int right) {
        if(left >= right) {
            return ;
        }
        //在此处进行优化1 :给定一个区间阈值, 使用直接插入排序排序数组
        if( right -left + 1 <= 7000) {
            //进行插入排序
            insertSortRange(arr,left,right);
            return;
        }
        //优化二: 三数取中法 找到头和尾与头尾对应的中间的下标,将数值为中间的那个数的下标返回
        int index = threeDight( arr,left,right);
        //将返回的中间值与第一个值进行交换, 使基准变为 数值为数组的中间值
        swap(arr,left,index);

        int privot = partition2(arr,left,right);
        quickSort2(arr,left,privot-1);
        quickSort2(arr,privot+1,right);

    }
    //三数取中法 : 找到三个数中数值为中间的那个数的下标
    private static int threeDight(int[] arr, int left, int right) {
         //找到中间下标
         int mid = left + ( (right - left) >>>1 );
         if( arr[left] > arr[right]) {
             if( arr[mid] > arr[left]) {
                 return left;
             } else if( arr[mid] < arr[right]) {
                 return right;
             } else {
                 return mid;
             }
         } else {
             if( arr[mid] > arr[right]) {
                 return right;
             } else if ( arr[mid] < arr[left]) {
                 return left;
             } else {
                 return mid;
             }
         }
    }
    public static void insertSortRange(int[] array ,int low ,int right) {
        for(int i =low+1;i <= right; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= 0 ; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    //array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    /**
     * 快速排序的非递归实现
     * 思路 :
     *    step1:  先对要排序的数组进行一次找基准划分, 而后根据这次的划分 ,判断当划分左边的元素为1个时,说明左边已经有序了,当右边的元素为1时, 右边有序
     *    step2:  当左边的元素个数不为1时, 借助一个栈, 将左边的划分的 最小下标 和 最大下标 放入栈中 , 右边元素个数不为1时 ,与左边相同的操作
     *    strp3:  当栈中元素不为空时, 弹出栈顶的两个元素 ,分别赋给 left 和 right 下标 , 再去进行划分找基准 入栈的操作,重复 step1 和 step2的操作.
     *            当栈为空时 ,说明左右数组已经有序 ,  数组排序完毕.
    */
    public static void quickSortNor( int []arr , int left ,int right) {
        Stack<Integer> stack = new Stack<>();
        int ret = partition2(arr , left ,right);
        //当left < ret -1 说明 左边的元素个数 不为1 , 将左边 划分区间的左右下标入栈
        if( left < ret - 1) {
            stack.push( left);
            stack.push( ret -1);
        }
        //reight > ret +1 说明 右边的元素个数 不为1 , 将右边 划分区间的左右下标入栈
        if( right > ret + 1) {
            stack.push( ret+1);
            stack.push( right);
        }
        //当栈不为空时 , 循环进行划分
        while( !stack.isEmpty()) {
            //弹出栈顶两个元素, 更新lfet 和 right
            right = stack.pop();
            left = stack.pop();

            //重复进行划分排序
            ret = partition2(arr , left ,right);
            if( left < ret - 1) {
                stack.push( left);
                stack.push( ret -1);
            }
            if( right > ret + 1) {
                stack.push( ret+1);
                stack.push( right);
            }
        }
    }

    /**
     * 归并排序 递归
     * 思想 : 分治思想  , 先将数组元素分解为一个个的元素 , 各个元素进行比较 ,根据大小再进行合并
     *  step1 : 先将数组进行分解 , 先找到中间位置 , 分别递归其 左边划分的数组, 和右边划分的数组,
     *          递归结束时, 数组被划分成一个一个的元素
     *  step2 : 选取两个分解的元素,按照大小将其存放到一个临时的数组中 , 将两个数合并到一个数组中 ,
     *          再将这个临时数组的值更新原来的数组, 得到排序的数组
     * @param
     */
    //strp1 : 递归进行分解
    public static void mergeSort( int arr[], int left , int right) {
        //终止条件 , 当左下标和右下标相遇时,说明只剩一个元素了 , 递归结束
        if( left >= right) {
            return ;
        }
        int mid = left + (( right - left) >>> 1);
        //此时mid是左边数组的最后一个元素的下标 , mid + 1是右边数组第一个元素的下标
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1,right);
        merge( arr, left, mid, right);
    }
    //step2 : 合并!
    public static void merge( int []arr, int left, int mid, int right) {
        int s1 = left; //左边数组的头
        int e1 = mid ;//左边数组的尾
        int s2 = mid + 1;//右边数组的头
        int e2 = right;//右边数组的尾
        int k = 0 ;//tmp数组的下标

        //创建临时数组 存放排序后的数组, 大小为 right-left+1
        int []tmp = new int[ right-left+1];
        //保证两个数组都有元素
        while( s1 <= e1 && s2 <= e2)  {
            //比较 arr[s1] 和 arr[s2]的大小 , 将小的放入tmp数组, 同时往后走
            if( arr[s1] <= arr[s2]) {
                tmp[k++] = arr[s1++];
            } else {
                tmp[k++] = arr[s2++];
            }
        }

        //此时 可能1个数组走完 , 令一个数组还有数, 且还有的数都是并当前tmp数组里的数大的, 直接存入tmp数组即可
        while( s1 <= e1 ) {
            tmp[k++] = arr[s1++];
        }

        while( s2<=e2 ) {
            tmp[k++] = arr[s2++];
        }

        //将 tmp 数组中排好序的值复制到arr中
        for (int i = 0; i < tmp.length; i++) {
            arr[i + left] = tmp[i];   // i+left 保证每次都是从 arr数组 未被更新的地方开始更新
        }
    }

    //归并排序 : 非递归的实现
    //思路 : 将数组分成 n 个组 , 每个组有gap个元素 , 每组元素两两进行比较排序合并
    public static void mergeSortNor(int[] array) {
        //gap从1开始 , 先让每组一个元素有序
        int gap = 1;
        while (gap < array.length) {
            for (int i = 0; i < array.length; i += 2*gap) {
                int left = i;
                int mid = left + gap - 1;
                //修正mid
                if(mid >= array.length) {
                    mid =  array.length-1;
                }
                int right = mid + gap;
                //修正right
                if(right >= array.length) {
                    right = array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap *= 2;
        }
    }

    /**
     * 非基于比较的排序 :  计数排序
     * 适用范围: 适用于数据量大, 但数据的数值范围小,数值大小集中的 数组排序
     * 思想 : 创建一个计数数组count , 将要排序数组arr的 每一个数作为 count数组的下标, 遍历arr数组, 其中一个数每出现一次,count数组对应的位置次数+1
     *       最后遍历输出count数组的下标, 得到排序好的数组
     * 时间复杂度: O( 数值范围 + n)
     * 空间复杂度: O( 范围 )
     * 步骤  :
     *      step1 : 找到arrary数组的最小值和最大值 , 确定数组的数值范围 range
     *      step2 : 根据范围 , 开辟 count数组
     *      step3 : 遍历array数组 , 进行计数
     *      step4 : 遍历count数组 , 对array数组进行更新
     * @param
     */

    public static void countSort( int []arr) {
        int min = arr[0];
        int max = arr[0];
        //step1: 先找最大值和最小值确定范围
        for (int i = 1; i < arr.length; i++) {
            if( arr[i] > max) {
                max = arr[i];
            }
            if( arr[i] < min) {
                min = arr[i];
            }
        }
        int range = max - min + 1;

        //step2: 创建count数组
        int [] count = new int[range];

        //step3: 遍历arr数组,进行计数
        for (int i=0; i<arr.length; i++) {
            count[ arr[i] - min ] ++;
        }

        //step4: 计数完成 , 遍历count数组 , 将array数组进行更新
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while( count[i] >0) {
                arr[index++] = i + min;    //此时 ,count数组的下标 + 范围 就是原来数组的值
                count[i]--;                  //相同的元素放在一起, 直到计数为0
            }
        }
    }
    //测试希尔排序
    public static void testShellSort(int[] array) {
        array = Arrays.copyOf(array,array.length);
        long startTime = System.currentTimeMillis();
        TestSort.shellSort(array);
        long endTime = System.currentTimeMillis();
        System.out.println("希尔排序："+ (endTime-startTime));
    }
    //测试插入排序
    public static void testInsertSort(int[] array) {
        array = Arrays.copyOf(array,array.length);
        long startTime = System.currentTimeMillis();
        TestSort.insertSort(array);
        long endTime = System.currentTimeMillis();
        System.out.println("插入排序："+ (endTime-startTime));
    }
    //测试选择排序
    public static void testSelectSort(int[] array) {
        array = Arrays.copyOf(array,array.length);
        long startTime = System.currentTimeMillis();
        TestSort.selectSort(array);
        long endTime = System.currentTimeMillis();
        System.out.println("选择排序："+ (endTime-startTime));
    }
    //测试堆排序
    public static void testHeapSort(int[] array) {
        array = Arrays.copyOf(array,array.length);
        long startTime = System.currentTimeMillis();
        TestSort.heapSort(array);
        long endTime = System.currentTimeMillis();
        System.out.println("堆排序："+ (endTime-startTime));
    }
    //测试冒泡排序
    public static void testBubbleSort(int[] array) {
        array = Arrays.copyOf(array,array.length);
        long startTime = System.currentTimeMillis();
        TestSort.bubbleSort2(array);
        long endTime = System.currentTimeMillis();
        System.out.println("冒泡排序："+ (endTime-startTime));
    }
    //测试快速排序
    public static void testQuickSort(int[] array) {
        array = Arrays.copyOf(array,array.length);
        long startTime = System.currentTimeMillis();
        TestSort.quickSort2(array,0,array.length-1);
        long endTime = System.currentTimeMillis();
        System.out.println("快速排序："+ (endTime-startTime));
    }
    //测试归并排序
    public static void testMergeSort(int[] array) {
        array = Arrays.copyOf(array,array.length);
        long startTime = System.currentTimeMillis();
        TestSort.mergeSort(array,0,array.length-1);
        long endTime = System.currentTimeMillis();
        System.out.println("归并排序："+ (endTime-startTime));
    }

    //测试计数排序
    public static void testcountSort(int[] array) {
        array = Arrays.copyOf(array,array.length);
        long startTime = System.currentTimeMillis();
        TestSort.countSort(array);
        long endTime = System.currentTimeMillis();
        System.out.println("计数排序："+ (endTime-startTime));
    }

    public static void main(String[] args) {
       int[] array = new int[10_0000];
        //int []array = { 5,4,8,7,2,3,20,55,100};
        countSort(array);
        //System.out.println(Arrays.toString(array));
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            //array[i] = i; //有序数组测试
            array[i] = random.nextInt(10000); //生成随机的无序数组测试
        }
        testShellSort(array);
        testInsertSort(array);
        testSelectSort(array);
        testHeapSort(array);
        testQuickSort(array);
        testMergeSort(array);
        //testBubbleSort(array);
        testcountSort(array);
    }


}